{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Paths That Can Form a Palindrome in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #tree #depth-first-search #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #树 #深度优先搜索 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPalindromePaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #树中可以形成回文的路径数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <strong>树</strong>（即，一个连通、无向且无环的图），<strong>根</strong> 节点为 <code>0</code> ，由编号从 <code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个节点组成。这棵树用一个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的数组 <code>parent</code> 表示，其中 <code>parent[i]</code> 为节点 <code>i</code> 的父节点，由于节点 <code>0</code> 为根节点，所以 <code>parent[0] == -1</code> 。</p>\n",
    "\n",
    "<p>另给你一个长度为 <code>n</code> 的字符串 <code>s</code> ，其中 <code>s[i]</code> 是分配给 <code>i</code> 和 <code>parent[i]</code> 之间的边的字符。<code>s[0]</code> 可以忽略。</p>\n",
    "\n",
    "<p>找出满足 <code>u &lt; v</code> ，且从 <code>u</code> 到 <code>v</code> 的路径上分配的字符可以 <strong>重新排列</strong> 形成 <strong>回文</strong> 的所有节点对&nbsp;<code>(u, v)</code> ，并返回节点对的数目。</p>\n",
    "\n",
    "<p>如果一个字符串正着读和反着读都相同，那么这个字符串就是一个 <strong>回文</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png\" style=\"width: 281px; height: 181px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>parent = [-1,0,0,1,1,2], s = \"acaabc\"\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>符合题目要求的节点对分别是：\n",
    "- (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。\n",
    "- (2,3)，路径上字符形成的字符串是 \"aca\" ，满足回文定义。\n",
    "- (1,5)，路径上字符形成的字符串是 \"cac\" ，满足回文定义。\n",
    "- (3,5)，路径上字符形成的字符串是 \"acac\" ，可以重排形成回文 \"acca\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>parent = [-1,0,0,0,0], s = \"aaaaa\"\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>任何满足 u &lt; v 的节点对 (u,v) 都符合题目要求。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == parent.length == s.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>对于所有 <code>i &gt;= 1</code> ，<code>0 &lt;= parent[i] &lt;= n - 1</code> 均成立</li>\n",
    "\t<li><code>parent[0] == -1</code></li>\n",
    "\t<li><code>parent</code> 表示一棵有效的树</li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-paths-that-can-form-a-palindrome-in-a-tree](https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-paths-that-can-form-a-palindrome-in-a-tree](https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,0,1,1,2]\\n\"acaabc\"', '[-1,0,0,0,0]\\n\"aaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        flag = [-1] * n\n",
    "        ans = 0\n",
    "        m = lambda x: 1 << (ord(x) - ord('a'))\n",
    "\n",
    "        def get_flag(i):\n",
    "            if i == -1: return 0\n",
    "            if flag[i] == -1:\n",
    "                flag[i] = get_flag(parent[i]) ^ m(s[i])\n",
    "            return flag[i]\n",
    "\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            f = get_flag(i)\n",
    "            ans += cnt[f]\n",
    "            for j in range(26):\n",
    "                ans += cnt[f ^ (1 << j)]\n",
    "            cnt[f] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        count = defaultdict(int)\n",
    "        N = len(parent)\n",
    "        bitset = [None] * N\n",
    "        ans = 0\n",
    "        def get_bitset(i):\n",
    "            if bitset[i] is not None:\n",
    "                return bitset[i]\n",
    "            p = parent[i]\n",
    "            if p == -1:\n",
    "                b = 0\n",
    "            else:\n",
    "                ci = ord(s[i]) - ord('a')\n",
    "                b = get_bitset(p) ^ (1 << ci)\n",
    "            bitset[i] = b\n",
    "            count[b] += 1\n",
    "            return b\n",
    "\n",
    "        for i in range(len(parent)):\n",
    "            get_bitset(i)\n",
    "        for k, v in count.items():\n",
    "            ans += v * (v - 1) // 2\n",
    "            x = k\n",
    "            while x:\n",
    "                lowbit = (x & (-x))\n",
    "                ans += v * count.get(k ^ lowbit, 0)\n",
    "                x -= lowbit\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(parent)\n",
    "        dp=[0]*n\n",
    "        used=[0]*n\n",
    "        for i in range(1,n):\n",
    "            dp[i]=(1<<(ord(s[i:i+1])-ord('a')))\n",
    "        def dfs(x):\n",
    "            nonlocal dp,used\n",
    "            if x==0:\n",
    "                return 0\n",
    "            if used[x]==1:\n",
    "                return dp[x]\n",
    "            if used[parent[x]]==0:\n",
    "                dfs(parent[x])\n",
    "            dp[x]=(dp[x]^dp[parent[x]])\n",
    "            used[x]=1\n",
    "            return dp[x]\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        map1=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            map1[dp[i]]+=1\n",
    "        res=0\n",
    "        print(map1)\n",
    "        for k,v in map1.items():\n",
    "            res+=(v*(v-1)//2)\n",
    "        tmp=0\n",
    "        for k,v in map1.items():\n",
    "            for j in range(26):\n",
    "                tmp+=(map1.get(k^(1<<j),0)*v)\n",
    "        return res+tmp//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic=dict()\n",
    "        X=dict()\n",
    "        c=0\n",
    "        for i in range(len(parent)):\n",
    "            x=0\n",
    "            start=i\n",
    "            while parent[start]!=-1  and X.get(start,None)==None:\n",
    "                x=x^1<<(ord(s[start])-ord('a'))\n",
    "                start=parent[start]\n",
    "            x=x^X.get(start,0)\n",
    "            X[i]=x\n",
    "            for i in range(26):\n",
    "                c+=dic.get((1<<i)^x,0)\n",
    "            c+=dic.get(x,0)\n",
    "            dic[x]=dic.get(x,0)+1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic=dict()\n",
    "        X=dict()\n",
    "        c=0\n",
    "        for i in range(len(parent)):\n",
    "            x=0\n",
    "            start=i\n",
    "            while parent[start]!=-1  and X.get(start,None)==None:\n",
    "                x=x^1<<(ord(s[start])-ord('a'))\n",
    "                start=parent[start]\n",
    "            x=x^X.get(start,0)\n",
    "            X[i]=x\n",
    "            for i in range(26):\n",
    "                c+=dic.get((1<<i)^x,0)\n",
    "            c+=dic.get(x,0)\n",
    "            dic[x]=dic.get(x,0)+1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic=dict()\n",
    "        X=dict()\n",
    "        c=0\n",
    "        for i in range(len(parent)):\n",
    "            x=0\n",
    "            start=i\n",
    "            while parent[start]!=-1  and X.get(start,None)==None:\n",
    "                x=x^1<<(ord(s[start])-ord('a'))\n",
    "                start=parent[start]\n",
    "            x=x^X.get(start,0)\n",
    "            X[i]=x\n",
    "            for i in range(26):\n",
    "                c+=dic.get((1<<i)^x,0)\n",
    "            c+=dic.get(x,0)\n",
    "            dic[x]=dic.get(x,0)+1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(s);_2,res,ans,mp,vis={chr(97+i):2**i for i in range(26)},[0]*n,0,{0:1},[0]*n;vis[0]=1\n",
    "        def dfs(u):\n",
    "            nonlocal _2,res,ans,mp,vis\n",
    "            if(not vis[parent[u]]):dfs(parent[u])\n",
    "            x=res[parent[u]]^_2[s[u]];res[u],vis[u]=x,1\n",
    "            for j,k in _2.items():ans+=mp.get(x^k,0)\n",
    "            mp[x]=mp.get(x,0)+1;ans+=mp[x]-1\n",
    "        for i in range(1,n):0 if(vis[i])else dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "\n",
    "        def dfs(i, b):\n",
    "            nonlocal res\n",
    "            if i:\n",
    "                b ^= 1 << slist[i]\n",
    "            rlist[i] = b\n",
    "            for j in tree[i]:\n",
    "                dfs(j, b)\n",
    "\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n * (n - 1) // 2\n",
    "        slist = [0] * n\n",
    "        rlist = [0] * n  # 节点的字符组合值（自 0 点）\n",
    "        for i, c in enumerate(s):\n",
    "            slist[i] = ord(c) - 97\n",
    "        tree = defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            tree[parent[i]].append(i)\n",
    "        # print(tree)\n",
    "        dfs(0, 0)\n",
    "        rlist.pop(0)\n",
    "        # print(rlist)\n",
    "        h = defaultdict(int)  # 回文: 数量\n",
    "        h_bit = defaultdict(set)  # 回文单数值: 回文集合\n",
    "        for i in rlist:\n",
    "            h[i] += 1\n",
    "            h_bit[i.bit_count()].add(i)\n",
    "        # print(h, h_bit)\n",
    "\n",
    "        # 先将距 0 点回文值为 0 或 1 的点数累加\n",
    "        res = h[0] + sum([h[i] for i in h_bit[1]])\n",
    "        # print(res)\n",
    "        # 对相同值的组合数累加\n",
    "        for i in h.values():\n",
    "            if i > 1:\n",
    "                res += i * (i - 1) // 2\n",
    "        # print(res)\n",
    "        # 对不同回文值的组合数累加\n",
    "        for c in h_bit:\n",
    "            if c - 1 not in h_bit:\n",
    "                continue\n",
    "            for i in h_bit[c]:\n",
    "                # 获得 i 去掉各 1 位上的 1\n",
    "                t = i\n",
    "                for j in range(c):\n",
    "                    # 逐个得到不同位的 1\n",
    "                    t1 = t & (-t)\n",
    "                    if (tc := i ^ t1) in h_bit[c - 1]:\n",
    "                        res += h[i] * h[tc]\n",
    "                    t ^= t1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic=dict()\n",
    "        X=dict()\n",
    "        c=0\n",
    "        def find(x):\n",
    "            if x in X:\n",
    "                return X[x]\n",
    "            if parent[x]==-1:\n",
    "                return 0\n",
    "            X[x]=1<<(ord(s[x])-ord('a'))^find(parent[x])\n",
    "            return X[x]\n",
    "        for i in range(len(parent)):\n",
    "            x=0\n",
    "            x=find(i)\n",
    "            for i in range(26):\n",
    "                c+=dic.get((1<<i)^x,0)\n",
    "            c+=dic.get(x,0)\n",
    "            dic[x]=dic.get(x,0)+1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic=dict()\n",
    "        X=dict()\n",
    "        c=0\n",
    "        def find(x):\n",
    "            if x in X:\n",
    "                return X[x]\n",
    "            if parent[x]==-1:\n",
    "                return 0\n",
    "            X[x]=1<<(ord(s[x])-ord('a'))^find(parent[x])\n",
    "            return X[x]\n",
    "        for i in range(len(parent)):\n",
    "            x=find(i)\n",
    "            for i in range(26):\n",
    "                c+=dic.get((1<<i)^x,0)\n",
    "            c+=dic.get(x,0)\n",
    "            dic[x]=dic.get(x,0)+1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        \n",
    "        # 从根到节点i路径上的字母的位掩码，某一位为1代表该字母有奇数个\n",
    "        @cache\n",
    "        def mask(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            return mask(parent[i]) ^ (1 << ord(s[i]) - ord('a'))\n",
    "        \n",
    "        count = Counter(mask(i) for i in range(n))  # 各种位掩码的个数\n",
    "        ans = 0\n",
    "        for k in count:\n",
    "            ans += count[k] * (count[k] - 1) // 2  # 所有字母都偶数个，有多少节点对\n",
    "            # 某一字母有奇数个，有多少节点对\n",
    "            for i in range(26):\n",
    "                if k ^ (1 << i) in count and k ^ (1 << i) >= k:\n",
    "                    ans += count[k] * count[k ^ (1 << i)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        @cache\n",
    "        def get(idx):\n",
    "            if idx == 0: return 0\n",
    "            return get(parent[idx]) ^ (1<< (ord(s[idx]) - ord('a')))\n",
    "        \n",
    "        vals = [get(x) for x in range(n)]\n",
    "        cnt = Counter()\n",
    "        res = 0\n",
    "        for x in vals:\n",
    "            res += cnt[x]\n",
    "            for i in range(26):\n",
    "                res += cnt[x ^ (1<<i)]\n",
    "            cnt[x] += 1\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        \n",
    "        # 从根到节点i路径上的字母的位掩码，某一位为1代表该字母有奇数个\n",
    "        @cache\n",
    "        def mask(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            return mask(parent[i]) ^ 1 << ord(s[i]) - ord('a')\n",
    "        \n",
    "        count = Counter(mask(i) for i in range(n))  # 各种位掩码的个数\n",
    "        ans = 0\n",
    "        for k, v in count.items():\n",
    "            ans += v * (v - 1) // 2  # 所有字母都偶数个，有多少节点对\n",
    "            # 某一字母有奇数个，有多少节点对\n",
    "            for i in range(26):\n",
    "                if k ^ 1 << i in count and k ^ 1 << i > k:\n",
    "                    ans += v * count[k ^ 1 << i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        \n",
    "        # 从根到节点i路径上的字母的位掩码，某一位为1代表该字母有奇数个\n",
    "        @cache\n",
    "        def mask(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            return mask(parent[i]) ^ 1 << ord(s[i]) - ord('a')\n",
    "        \n",
    "        count = Counter(mask(i) for i in range(n))  # 各种位掩码的个数\n",
    "        ans = 0\n",
    "        for k in count:\n",
    "            ans += count[k] * (count[k] - 1) // 2  # 所有字母都偶数个，有多少节点对\n",
    "            # 某一字母有奇数个，有多少节点对\n",
    "            for i in range(26):\n",
    "                if k ^ 1 << i in count and k ^ 1 << i >= k:\n",
    "                    ans += count[k] * count[k ^ 1 << i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i==0:\n",
    "                return 0\n",
    "            return dfs(parent[i]) ^ (1 << (ord(s[i]) - ord('a')))\n",
    "\n",
    "        n = len(parent)\n",
    "        a = Counter(dfs(i) for i in range(n))\n",
    "        ans = 0\n",
    "        for k, cnt in a.items():\n",
    "            ans += cnt * (cnt - 1)\n",
    "            s = sum(a[k ^ (1<<i)] for i in range(26))\n",
    "            ans += cnt * s\n",
    "        ans //= 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i==0:\n",
    "                return 0\n",
    "            return dfs(parent[i]) ^ (1 << (ord(s[i]) - ord('a')))\n",
    "\n",
    "        n = len(parent)\n",
    "        a = [dfs(i) for i in range(n)]\n",
    "        ans = 0\n",
    "        for i_ in range(26):\n",
    "            a.sort()\n",
    "            # print(i_, [bin(x) for x in a])\n",
    "            prevk, prevcnt = 0, 0\n",
    "            for k, g in groupby(a):\n",
    "                cnt = sum(1 for _ in g)\n",
    "                if i_ == 0:\n",
    "                    ans += cnt * (cnt - 1) // 2\n",
    "                    # print('x', ans, cnt)\n",
    "                if k ^ prevk == 1:\n",
    "                    ans += prevcnt * cnt\n",
    "                    # print('y', ans, prevcnt, cnt)                    \n",
    "                prevk, prevcnt = k, cnt\n",
    "                \n",
    "            # rotate 1 bit\n",
    "            for i in range(n):\n",
    "                a[i] = (a[i] >> 1) | ((a[i] & 1) << 25)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        n = len(parent)\n",
    "        for i in range(1, n):\n",
    "            graph[parent[i]].append(i)\n",
    "        res = 0\n",
    "        counter = collections.Counter()\n",
    "        counter[0] = 1 \n",
    "        def dfs(node, XOR):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                bit = ord(s[nei]) - ord('a')\n",
    "                new = XOR ^ (1 << bit)\n",
    "                res += counter[new]\n",
    "                for val in range(26):\n",
    "                    res += counter[new ^ (1 << val)]\n",
    "                counter[new] += 1\n",
    "                dfs(nei, new)\n",
    "        dfs(0, 0)\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[parent[i]].append(i)\n",
    "        dic = collections.Counter()\n",
    "        dic[0] = 1\n",
    "        res = 0\n",
    "        def dfs(node, XOR):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                bit = ord(s[nei]) - ord('a')\n",
    "                new = XOR ^ (1 << bit) \n",
    "                res += dic[new]\n",
    "                for v in range(26):\n",
    "                    res += dic[new ^ (1 << v)]\n",
    "                dic[new] += 1 \n",
    "                dfs(nei, new)\n",
    "        dfs(0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[parent[i]].append(i)\n",
    "        res = 0\n",
    "        counter = collections.Counter()\n",
    "        counter[0] = 1 \n",
    "        def dfs(node, XOR):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                bit = 1 << (ord(s[nei]) - ord('a')) \n",
    "                new = XOR ^ bit\n",
    "                res += counter[new]\n",
    "                for v in range(26):\n",
    "                    res += counter[new ^ (1 << v)]\n",
    "                counter[new] += 1 \n",
    "                dfs(nei, new)\n",
    "        dfs(0, 0)\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[parent[i]].append(i)\n",
    "        res = 0\n",
    "        counter = collections.Counter()\n",
    "        counter[0] = 1 \n",
    "        def dfs(node, XOR):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                bit = 1 << (ord(s[nei]) - ord('a')) \n",
    "                new = XOR ^ bit\n",
    "                res += counter[new]\n",
    "                for v in range(26):\n",
    "                    res += counter[new ^ (1 << v)]\n",
    "                counter[new] += 1 \n",
    "                dfs(nei, new)\n",
    "        dfs(0, 0)\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "        res = 0\n",
    "        cnt = Counter()\n",
    "        def dfs(v, xor):\n",
    "            nonlocal res\n",
    "            res = res + cnt[xor] + sum([ cnt[xor^(1<<i)] for i in range(26)])\n",
    "            cnt[xor]+=1\n",
    "            for w in g[v]:\n",
    "                bit = 1<<(ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                dfs(w, x)\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(parent)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            e[parent[i]].append(i)\n",
    "        res=0\n",
    "        cnt=Counter([0])\n",
    "        def dfs(u:int,x:int)->None:\n",
    "            nonlocal res\n",
    "            for v in e[u]:\n",
    "                now=x^(1<<(ord(s[v])-ord('a')))\n",
    "                res+=cnt[now]+(sum(cnt[now^(1<<i)] for i in range(26)))\n",
    "                cnt[now]+=1\n",
    "                dfs(v,now)\n",
    "        dfs(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(parent)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            e[parent[i]].append(i)\n",
    "        res=0\n",
    "        cnt=Counter([0])\n",
    "        def dfs(u:int,x:int)->None:\n",
    "            nonlocal res\n",
    "            for v in e[u]:\n",
    "                now=x^(1<<(ord(s[v])-ord('a')))\n",
    "                res+=cnt[now]+(sum(cnt[now^(1<<i)] for i in range(26)))\n",
    "                cnt[now]+=1\n",
    "                dfs(v,now)\n",
    "        dfs(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            bit  = 1 <<(ord(s[i]) - ord('a'))\n",
    "            g[parent[i]].append((i, bit))\n",
    "\n",
    "        ans  = 0\n",
    "        cnt = Counter()\n",
    "\n",
    "        def dfs(v: int, xor: int) :\n",
    "            nonlocal ans\n",
    "            ans += cnt[xor]\n",
    "            for i in range(26):\n",
    "                ans += cnt[xor ^ (1 << i)]\n",
    "            cnt[xor] += 1\n",
    "            for w , t in g[v]:\n",
    "                dfs(w, xor ^ t)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPalindromePaths(self, parent, s):\n",
    "        \"\"\"\n",
    "        :type parent: List[int]\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # n = len(parent)\n",
    "        # res = 0\n",
    "        # child_d = {}\n",
    "        # for i in range(1, n):\n",
    "        #     p = parent[i]\n",
    "        #     if p not in child_d:\n",
    "        #         child_d[p] = []\n",
    "        #     child_d[p].append((i, 1 << (ord(s[i])-ord('a'))))\n",
    "        # # for r, st in child_d.items():\n",
    "        # #     for j in st:\n",
    "        # #         print(r, j[0], chr(j[1]+ord(\"a\")))\n",
    "        # record = {0: 1}\n",
    "        # def dfs(i, state):\n",
    "        #     nonlocal res\n",
    "        #     if i > 0:\n",
    "        #         even = record.get(state)\n",
    "        #         if even:\n",
    "        #             res += even\n",
    "        #         for alpha in range(26):\n",
    "        #             odd = record.get(state ^ (1 << alpha))\n",
    "        #             if odd:\n",
    "        #                 res += odd\n",
    "        #         if even:\n",
    "        #             record[state] += 1\n",
    "        #         else:\n",
    "        #             record[state] = 1\n",
    "        #         # for r, st in record.items():\n",
    "        #         #     print(bin(r), st)\n",
    "        #     for c in child_d.get(i,[]):\n",
    "        #         dfs(c[0], state ^ (c[1]))\n",
    "        # dfs(0,0)\n",
    "        # return res\n",
    "\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(s)\n",
    "        g=[[] for _ in  range(n)]\n",
    "        for i in range(1,n):\n",
    "            g[parent[i]].append(i)\n",
    "        \n",
    "        ans=0\n",
    "        cnt=Counter([0])\n",
    "        def dfs(v,xor):\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit=1<<(ord(s[w])-ord('a'))\n",
    "                x=xor^bit\n",
    "                ans+=cnt[x]+sum(cnt[x^(1<<i)]for i in range(26))\n",
    "                cnt[x]+=1\n",
    "                dfs(w,x)\n",
    "        dfs(0,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(s)\n",
    "        g=[[] for _ in  range(n)]\n",
    "        for i in range(1,n):\n",
    "            g[parent[i]].append(i)\n",
    "        \n",
    "        ans=0\n",
    "        cnt=Counter([0])\n",
    "        def dfs(v,xor):\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit=1<<(ord(s[w])-ord('a'))\n",
    "                x=xor^bit\n",
    "                ans+=cnt[x]+sum(cnt[x^(1<<i)]for i in range(26))\n",
    "                cnt[x]+=1\n",
    "                dfs(w,x)\n",
    "        dfs(0,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            bit = 1 << (ord(s[i]) - ord('a'))\n",
    "            g[parent[i]].append((i, bit))\n",
    "        ans = 0\n",
    "        cnt =Counter()\n",
    "        def dfs(v, xor):\n",
    "            nonlocal ans\n",
    "            ans += cnt[xor]\n",
    "            for i in range(26):\n",
    "                ans += cnt[xor ^ (1 << i)]\n",
    "            cnt[xor] += 1\n",
    "            for to, x in g[v]:\n",
    "                dfs(to, x ^ xor)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(s)\n",
    "        g=[[] for _ in  range(n)]\n",
    "        for i in range(1,n):\n",
    "            g[parent[i]].append(i)\n",
    "        \n",
    "        ans=0\n",
    "        cnt=Counter([0])\n",
    "        def dfs(v,xor):\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit=1<<(ord(s[w])-ord('a'))\n",
    "                x=xor^bit\n",
    "                ans+=cnt[x]+sum(cnt[x^(1<<i)]for i in range(26))\n",
    "                cnt[x]+=1\n",
    "                dfs(w,x)\n",
    "        dfs(0,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, len(s)):\n",
    "            bit = 1 << (ord(s[i]) - ord('a'))\n",
    "            g[parent[i]].append((i, bit))\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        def dfs(v: int, xor: int):\n",
    "            nonlocal ans\n",
    "            ans += cnt[xor]\n",
    "            for i in range(26):\n",
    "                ans += cnt[xor ^ (1 << i)]\n",
    "            cnt[xor] += 1\n",
    "            for to, w in g[v]:\n",
    "                dfs(to, w ^ xor)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(parent)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            e[parent[i]].append(i)\n",
    "        ans=0\n",
    "        cnt=Counter([0])\n",
    "        def dfs(u:int,xor:int)->None:\n",
    "            nonlocal ans\n",
    "            for v in e[u]:\n",
    "                pos=1<<(ord(s[v])-ord('a'))\n",
    "                x=xor^pos\n",
    "                ans+=cnt[x]+sum([cnt[x^(1<<i)] for i in range(26)])\n",
    "                cnt[x]+=1\n",
    "                dfs(v,x)\n",
    "        dfs(0,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, len(s)):\n",
    "            bit = 1 << (ord(s[i]) - ord('a'))\n",
    "            g[parent[i]].append((i, bit))\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        def dfs(v: int, xor: int):\n",
    "            nonlocal ans\n",
    "            ans += cnt[xor]\n",
    "            for i in range(26):\n",
    "                ans += cnt[xor ^ (1 << i)]\n",
    "            cnt[xor] += 1\n",
    "            for to, w in g[v]:\n",
    "                dfs(to, w ^ xor)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0]) \n",
    "\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, len(s)):\n",
    "            bit = 1 << (ord(s[i]) - ord('a'))\n",
    "            g[parent[i]].append((i, bit))\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        def dfs(v: int, xor: int):\n",
    "            nonlocal ans\n",
    "            ans += cnt[xor]\n",
    "            for i in range(26):\n",
    "                ans += cnt[xor ^ (1 << i)]\n",
    "            cnt[xor] += 1\n",
    "            for to, w in g[v]:\n",
    "                dfs(to, w ^ xor)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "        def dfs(v: int, xor: int) -> None:\n",
    "            nonlocal ans\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                dfs(w, x)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        cnt = Counter([0])  # 一条「空路径」\n",
    "        def dfs(v: int, xor: int) -> int:\n",
    "            res = 0\n",
    "            for w in g[v]:\n",
    "                bit = 1 << (ord(s[w]) - ord('a'))\n",
    "                x = xor ^ bit\n",
    "                res += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))\n",
    "                cnt[x] += 1\n",
    "                res += dfs(w, x)\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        # 一个字符串最多有26种字母, 回文串只能有 0 个 或 1 个不成对的字母\n",
    "        # 记录这26种字母集合的奇偶性,表示为 26bit的二进制数字\n",
    "        n=len(parent)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for nd, p in enumerate(parent):\n",
    "            if p<0:continue # -1索引:python搞不好成环\n",
    "            g[p].append((nd, 1<<(ord(s[nd])-ord('a'))))\n",
    "        cnt=Counter()\n",
    "        # 从根节点出发, 经过的点的路径字符串表示为 一个二进制数字\n",
    "        # 使用先序遍历, 不同分支的两个点之间的路径字符串 nd1--LCA--nd2\n",
    "        # 实际上是root-nd1, root-nd2, 减去公共的2个root--LCA\n",
    "        # 使用异或的情况下 nd1--nd2 的表示字符串 是 根到nd1的值异或根到nd2的值\n",
    "        # 对于先序遍历到的任何节点,存储 根到nd的值\n",
    "        # 如果之前存储的任何一个或几个值,与当前的nd的差, 所表示的字符串符合答案要求\n",
    "        # 那么, 这几个值代表的点 到nd 是存在一个回文子串\n",
    "        def dfs(nd,laststr):\n",
    "            ans=0\n",
    "            if laststr in cnt:\n",
    "                ans+=cnt[laststr]\n",
    "            for i in range(26):\n",
    "                if (1<<i)^laststr in cnt:\n",
    "                    ans+=cnt[(1<<i)^laststr]\n",
    "            cnt[laststr]+=1\n",
    "            for nd1,val in g[nd]:\n",
    "                ans+=dfs(nd1, laststr^val)\n",
    "            return ans\n",
    "        return dfs(0,0)  # (节点0, 空字符串)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic = dict(zip('abcdefghijklmnopqrstuvwxyz', [1 << i for i in range(26)]))\n",
    "        length = len(parent)\n",
    "        graph = [[] for i in range(length)]\n",
    "        for i in range(1, length):\n",
    "            graph[parent[i]].append(i)\n",
    "        count = Counter([0])\n",
    "        def dfs(p, xor):\n",
    "            cnt = 0\n",
    "            for child in graph[p]:\n",
    "                x = xor ^ dic[s[child]]\n",
    "                cnt += count[x] + sum(count[x ^ value] for value in dic.values())\n",
    "                count[x] += 1\n",
    "                cnt += dfs(child, x)\n",
    "            return cnt\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic = dict(zip('abcdefghijklmnopqrstuvwxyz', [1 << i for i in range(26)]))\n",
    "        length = len(parent)\n",
    "        graph = [[] for i in range(length)]\n",
    "        for i in range(1, length):\n",
    "            graph[parent[i]].append(i)\n",
    "        count = Counter([0])\n",
    "        def dfs(p, xor):\n",
    "            cnt = 0\n",
    "            for child in graph[p]:\n",
    "                x = xor ^ dic[s[child]]\n",
    "                cnt += count[x] + sum(count[x ^ value] for value in dic.values())\n",
    "                count[x] += 1\n",
    "                cnt += dfs(child, x)\n",
    "            return cnt\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        dic = dict(zip('abcdefghijklmnopqrstuvwxyz', [1 << i for i in range(26)]))\n",
    "        length = len(parent)\n",
    "        graph = [[] for i in range(length)]\n",
    "        for i in range(1, length):\n",
    "            graph[parent[i]].append(i)\n",
    "        count = Counter([0])\n",
    "        def dfs(p, xor):\n",
    "            cnt = 0\n",
    "            for child in graph[p]:\n",
    "                x = xor ^ dic[s[child]]\n",
    "                cnt += count[x] + sum(count[x ^ (1 << i)] for i in range(26))\n",
    "                count[x] += 1\n",
    "                cnt += dfs(child, x)\n",
    "            return cnt\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            g[parent[i]].append(i)\n",
    "        \n",
    "        @cache\n",
    "        def get(idx):\n",
    "            if not idx: return 0\n",
    "            v = 1 << (ord(s[idx]) - ord('a'))\n",
    "            return v ^ get(parent[idx])\n",
    "\n",
    "        vals = [get(x) for x in range(n)]\n",
    "\n",
    "        cnt = defaultdict(int)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            res += cnt[vals[i]]\n",
    "            for j in range(26):\n",
    "                res += cnt[vals[i] ^ (1<<j)]\n",
    "            cnt[vals[i]] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(parent)\n",
    "        g=defaultdict(list)\n",
    "        for i,v in enumerate(parent):\n",
    "            g[v].append(i)\n",
    "        \n",
    "        def dfs(u,bitmask):\n",
    "            print(u,bitmask)\n",
    "            cnt[bitmask]+=1\n",
    "            for v in g[u]:\n",
    "                dfs(v,bitmask^(1<<(ord(s[v])-97)))\n",
    "\n",
    "        cnt=Counter()\n",
    "        dfs(0,1<<(ord(s[0])-97))\n",
    "        res=0\n",
    "        for k,v in cnt.items():\n",
    "            res+=v*(v-1)\n",
    "            for i in range(26):\n",
    "                res+=cnt[k]*cnt[k^(1<<i)]\n",
    "        return res//2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n=len(parent)\n",
    "        g=defaultdict(list)\n",
    "        for i,v in enumerate(parent):\n",
    "            g[v].append(i)\n",
    "        \n",
    "        def dfs(u,bitmask):\n",
    "            print(u,bitmask)\n",
    "            cnt[bitmask]+=1\n",
    "            for v in g[u]:\n",
    "                dfs(v,bitmask^(1<<(ord(s[v])-97)))\n",
    "\n",
    "        cnt=Counter()\n",
    "        dfs(0,0)\n",
    "        res=0\n",
    "        for k,v in cnt.items():\n",
    "            res+=v*(v-1)\n",
    "            for i in range(26):\n",
    "                res+=cnt[k]*cnt[k^(1<<i)]\n",
    "        return res//2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, p: List[int], s: str) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for j in range(len(p)):\n",
    "            if p[j]!=-1:\n",
    "                g[p[j]].append(j) \n",
    "        self.ans = 0 \n",
    "        c = Counter()\n",
    "        def dfs(x, pre):\n",
    "            if p[x]!=-1:\n",
    "                t = ord(s[x])-97\n",
    "                pre = pre^(1<<t)\n",
    "            self.ans += c[pre]\n",
    "            for j in range(26):\n",
    "                self.ans += c[pre^(1<<j)] \n",
    "            c[pre] += 1 \n",
    "            for j in g[x]:\n",
    "                dfs(j, pre)  \n",
    "        dfs(0, 0)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        \n",
    "        @cache\n",
    "        def get(idx):\n",
    "            if not idx: return 0\n",
    "            v = 1 << (ord(s[idx]) - ord('a'))\n",
    "            return v ^ get(parent[idx])\n",
    "\n",
    "        vals = [get(x) for x in range(n)]\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            res += cnt[vals[i]]\n",
    "            for j in range(26):\n",
    "                res += cnt[vals[i] ^ (1<<j)]\n",
    "            cnt[vals[i]] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        dic = collections.Counter()\n",
    "        dic[0] = 1 \n",
    "        res = 0\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[parent[i]].append(i)\n",
    "        def dfs(node, XOR):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                new = XOR ^ (1 << (ord(s[nei]) - ord('a')))\n",
    "                res += dic[new]\n",
    "                for val in range(26):\n",
    "                    res += dic[new ^ (1 << val)]\n",
    "                dic[new] += 1 \n",
    "                dfs(nei, new)\n",
    "        dfs(0, 0)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        dic = collections.Counter()\n",
    "        dic[0] = 1 \n",
    "        res = 0\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[parent[i]].append(i)\n",
    "        def dfs(node, XOR):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                new = XOR ^ (1 << (ord(s[nei]) - ord('a')))\n",
    "                res += dic[new]\n",
    "                for val in range(26):\n",
    "                    res += dic[new ^ (1 << val)]\n",
    "                dic[new] += 1 \n",
    "                dfs(nei, new)\n",
    "        dfs(0, 0)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPalindromePaths(self, parent, s):\n",
    "        \"\"\"\n",
    "        :type parent: List[int]\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(parent)\n",
    "        res = 0\n",
    "        child_d = {}\n",
    "        for i in range(1, n):\n",
    "            p = parent[i]\n",
    "            if p not in child_d:\n",
    "                child_d[p] = []\n",
    "            child_d[p].append((i, 1 << (ord(s[i])-ord('a'))))\n",
    "        # for r, st in child_d.items():\n",
    "        #     for j in st:\n",
    "        #         print(r, j[0], chr(j[1]+ord(\"a\")))\n",
    "        record = {0: 1}\n",
    "        def dfs(i, state):\n",
    "            nonlocal res\n",
    "            if i > 0:\n",
    "                even = record.get(state)\n",
    "                if even:\n",
    "                    res += even\n",
    "                for alpha in range(26):\n",
    "                    odd = record.get(state ^ (1 << alpha))\n",
    "                    if odd:\n",
    "                        res += odd\n",
    "                if even:\n",
    "                    record[state] += 1\n",
    "                else:\n",
    "                    record[state] = 1\n",
    "                # for r, st in record.items():\n",
    "                #     print(bin(r), st)\n",
    "            for c in child_d.get(i,[]):\n",
    "                dfs(c[0], state ^ (c[1]))\n",
    "        dfs(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        def g(node, ls):\n",
    "            ns = ls ^ (1 << (ord(s[node]) - ord(\"a\")))\n",
    "            self.res += has[ns]\n",
    "            for i in range(26):\n",
    "                self.res += has[ns ^ (1<<i)]\n",
    "            has[ns] += 1\n",
    "            for i in dc[node]:\n",
    "                g(i, ns)\n",
    "        self.res = 0\n",
    "        dc = defaultdict(list)\n",
    "        has = defaultdict(int)\n",
    "        for i,v in enumerate(parent):\n",
    "            dc[v].append(i)\n",
    "        g(0, (1 << (ord(s[0]) - ord(\"a\"))))\n",
    "        # print(has)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countPalindromePaths(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        path = [0] * n\n",
    "        d = defaultdict(lambda: 0)\n",
    "        e = defaultdict(list)\n",
    "        for i, pi in enumerate(parent[1:], 1):\n",
    "            e[pi].append(i)\n",
    "        d[0] = 1\n",
    "        def dfs(node):\n",
    "            for i in e[node]:\n",
    "                path[i] = path[node] ^ (1 << ord(s[i]) - ord('a'))\n",
    "                d[path[i]] += 1\n",
    "                dfs(i)\n",
    "        dfs(0)\n",
    "        cnt = 0\n",
    "        # print(path)\n",
    "        # print(d)\n",
    "        for i in range(n):\n",
    "            cnt += d[path[i]] - 1\n",
    "            for j in range(26):\n",
    "                cnt += d[path[i] ^ (1 << j)]\n",
    "            # print(i, cnt)\n",
    "        return cnt >> 1\n",
    "            \n",
    "                \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
